﻿#define _CRT_SECURE_NO_WARNINGS 1 //安心，加油！



#define _CRT_SECURE_NO_WARNINGS 1 //安心，加油！

#include"标头.h"
#include<vector>

//AVL树的概念(更多看资料去搜)
//AVL树是最先发明的⾃平衡⼆叉查找树，AVL是⼀颗空树，或者具备下列性质的⼆叉搜索树：它的
//左右⼦树都是AVL树，且左右⼦树的⾼度差的绝对值不超过1。AVL树是⼀颗⾼度平衡搜索⼆叉树，
//通过控制⾼度差去控制平衡


void TestAVLTree1()
{
	AVLTree<int, string> t;
	int a1[] = { 10, 20, 30 };
	int a2[] = { 30, 20, 10 };
	int a3[] = { 30, 10, 20 };
	int a4[] = { 10, 30, 20 };
	int a5[] = { 50, 30, 70, 20, 40, 60, 80, 10, 25 };
	int a6[] = { 1, 2, 3, 4, 5, 6, 7 };
	int a7[] = { 40, 20, 60, 10, 30, 50, 70, 5, 15, 25, 35 };

	for (auto e : a5)
	{
		t.Insert({ e, "anxin" });
	}
	t.InOrder();
	cout << t.IsBalanceTree() << endl;
}

void TestAVLTree2()
{
	const int N = 1000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}

	size_t begin2 = clock();
	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
	size_t end2 = clock();

	cout << "Insert:" << end2 - begin2 << endl;
	cout << t.IsBalanceTree() << endl;

	cout << "Height:" << t.Height() << endl;
	cout << "Size:" << t.Size() << endl;

	size_t begin1 = clock();
	// 确定在的值
	for (auto e : v)
	{
		t.Find(e);
	}
	// 随机值
	/*for (size_t i = 0; i < N; i++)
	{
		t.Find((rand() + i));
	}*/
	size_t end1 = clock();
	cout << "Find:" << end1 - begin1 << endl;
}

//AVL树实现
int main()
{
	//TestAVLTree1();

	TestAVLTree2();

	return 0;
}











